链式队列Queue——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

LinkedQueue.h 头文件

#ifndef LINKEDQUEUE_H_INCLUDED
#define LINKEDQUEUE_H_INCLUDED

#include "Entitys.h"

//************************************************************************************************************************************************************************
//
//      类名：链表队列(LinkedQueue)
//
//      概述：一个可复用的链表队列，存储结构采用链表实现，可存储字符或整数。
//
//      说明：采用链表存储结构，队列的容量没限制，入队出队时间复杂度为O(1)
//
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//
//                                                                 队列节点结构体(QueueNode)
//
//========================================================================================================================================================================
template <typename T>
struct QueueNode
{
    T data;             //队列节点数据
    QueueNode* next;    //下一个队列节点指针
};

//========================================================================================================================================================================
//
//                                                                链表队列结构体(LinkedQueue)
//
//========================================================================================================================================================================
template <typename T>
struct LinkedQueue{
    //------------------------------------------------------------------------------------------------------
    //                                          私有成员                                                ||
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）   ||
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        QueueNode<T> *head = nullptr;   // 队列头指针
        QueueNode<T> *tail = nullptr;   // 队列尾指针
        int qty = 0;                    // 用于跟踪队列中的元素数量

        //---------------声明私有成员函数---------------



    //------------------------------------------------------------------------------------------------------
    //                                          公共成员                                                ||
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）     ||
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        LinkedQueue() {
            qty = 0;
        }

        int isEmpty();                  // 判断队列是否为空
        int isFull();                   // 判断队列是否已满
        T getHead();                    // 获取队列头元素（不弹出）
        T getTail();                    // 获取队列尾元素（不弹出）
        void enQueue(const T& value);  // 入队操作（在队列尾入队）
        T deQueue();                    // 出队操作（返回队列头元素）
        int getSize();                  // 获取队列大小
        void print();                  // 打印队列数据
        void destroyQueue();           // 手动销毁整个栈（防止内存泄漏）

        // 析构函数：自动销毁栈，避免内存泄漏
        ~LinkedQueue() {
            destroyQueue();
        }
};

#endif // LINKEDQUEUE_H_INCLUDED
                

LinkedQueue.cpp 程序代码

#include <iostream>
#include"LinkedQueue.h"

//---------------实现公共成员函数---------------

// 判断队列是否为空
template <typename T>
int LinkedQueue<T>::isEmpty()
{
    return qty == 0;
}

// 判断队列是否已满
template <typename T>
int LinkedQueue<T>::isFull()
{
    return -1;
}

// 获取队列头元素（不弹出）
template <typename T>
T LinkedQueue<T>::getHead()
{
    if (isEmpty()) {
        return T();
    }
    return head->data;
}

// 获取队列尾元素（不弹出）
template <typename T>
T LinkedQueue<T>::getTail()
{
    if (isEmpty()) {
        return T();;
    }
    return tail->data;
}

// 入队操作（在队列尾入队）
template <typename T>
void LinkedQueue<T>::enQueue(const T& value)
{
    QueueNode<T> *p = new QueueNode<T>;
    p->data = value;
    p->next = nullptr;
    if(isEmpty())
    {
        head = p;
        tail = p;
    }
    else
    {
        tail->next = p;
        tail = p;
    }
    qty++;
}

// 出队操作（返回队列头元素）
template <typename T>
T LinkedQueue<T>::deQueue()
{
    T value;
    if(isEmpty())
    {
        printf("队列为空，无法出队。\n");
        return T();;
    }

    QueueNode<T> *p = head;
    head = p->next;
    value = p->data;
    delete(p);
    qty--;

    return value;
}

// 获取队列大小
template template <typename T>
int LinkedQueue<T>::getSize()
{
    return qty;
}

// 打印队列数据
template <typename T>
void LinkedQueue<T>::print()
{
    printf("队列内容：");

    QueueNode<T> *p = head;
    if(p == nullptr)
    {
        printf("队列为空！无法遍历。\n");
        return;
    }
    while(p != nullptr)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 销毁整个栈（防止内存泄漏）
template <typename T>
void LinkedQueue<T>::destroyQueue()
{
    while(head != nullptr)
    {
        QueueNode<T> *p = head;
        head = p->next;
        delete(p);
        qty--;
    }
    printf("\n===== 队列内存已全部释放 =====\n");
}       

// 显式实例化常用类型（避免链接错误，可选）
template class LinkedQueue<int>;
template class LinkedQueue<char>;
template class LinkedQueue<float>;
template class LinkedQueue<std::string>;
template class LinkedQueue<Student>; // 新增：显式实例化Student类型
template class LinkedQueue<Pos>; // 新增：显式实例化Pos类型
template class LinkedQueue<PrintTask>; // 新增：显式实例化PrintTask类型

main.cpp 测试代码

#include "LinkedQueue.h"
#include <iostream>
#include <string>

int main() {
    LinkedQueue<int> queues;

    // 1. 入队测试
    printf("\n=== 入队测试 ===\n");
    queues.enQueue(1);
    queues.enQueue(2);
    queues.enQueue(3);
    queues.enQueue(4);
    queues.enQueue(5);
    printf("入队1、2、3、4、5后：\n");
    queues.print();

    // 2. 出队测试
    printf("\n=== 出队测试 ===\n");
    printf("出队3次：");
    printf("%d ",queues.deQueue());
    printf("%d ",queues.deQueue());
    printf("%d \n",queues.deQueue());
    printf("出队后");
    queues.print();
    
    return 0;
}

输出结果

=== 入队测试 ===
入队1、2、3、4、5后：
队列内容：1 2 3 4 5

=== 出队测试 ===
出队3次：1 2 3
出队后队列内容：4 5

===== 队列内存已全部释放 =====
    

六、注意事项

七、应用场景

• 层级 / 顺序处理的场景：二叉树层序遍历、图的 BFS、任务排队 → 队列保证按顺序处理；
• 最短路径 / 最少步数校验的场景：迷宫最短路径、无权图最短路径 → BFS 的层级特性天然适配最短路
• 循环 / 绕圈的场景：约瑟夫环、滑动窗口 → 队列的循环特性模拟绕圈。

八、总结

• 队列是 先进先出（FIFO）的线性数据结构，仅允许在队尾入队、队头出队，具有操作限制性；
• 按实现方式分为顺序队列（数组）和链式队列（链表），按功能扩展分为循环队列、双端队列、优先级队列等，其中循环队列解决了普通顺序队列的空间浪费问题；
• 核心操作的时间复杂度均为 O (1)，顺序队列优势在于高效访问，链式队列优势在于动态扩容；
• 广泛应用于任务调度、异步处理、BFS 算法、消息队列等场景，是计算机科学中不可或缺的基础数据结构；
• 与栈的核心区别在于进出规则，队列是 “先进先出”（双端操作），栈是 “先进后出”（单端操作）。

本教程通过代码解析和实战示例，覆盖了队列的核心原理、关键操作实现和实际使用场景。队列作为基础数据结构，在缓存机制、任务调度、消息队列等场景中有着广泛应用，掌握链表队列的实现，是深入学习更复杂数据结构（如优先级队列）的重要基础。